#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    void reorderList(ListNode* head) {
        if (head->next == nullptr || head->next->next == nullptr) return;
        ListNode* phead;
        phead = new ListNode();
        ListNode* cur = head;
        int k = 0;
        while (cur) {
            ListNode* node = new ListNode(cur->val);
            node->next = phead->next;
            phead->next = node;
            k++;
            cur = cur->next;
        }
        int n = (k - 1) / 2;
        cur = head;
        ListNode* cur2 = head->next;
        ListNode* dest = phead->next;
        int f = 0;
        while (f < n) {
            ListNode* node = new ListNode(dest->val);
            node->next = cur2;
            cur->next = node;
            cur = cur->next->next;
            f++;
            if (k % 2 && f == n) break;
            cur2 = cur2->next;
            dest = dest->next;

        }

        cur2->next = nullptr;
    }
};